#include <vector>

using namespace std;


/* 最长递增子序列 */
class Solution {
public:
    // DP: L[j] is the length of the longest increasing subsequence
    //     that definitely includes nums[j].
    // Recurrence Relation:
    //     L[j] = max{L[k]+1, if k<j and nums[k]<nums[j] else 1}
    int lengthOfLIS_DP(vector<int>& nums) {  // O(n^2)  O(n)
        int n = nums.size();
        if (n == 1) return 1;
        vector<int> L(n, 0);
        // L[0] = 1;
        for (int i=0; i<n; ++i) {
            int max_sofar = 1;
            for (int j=0; j<i; ++j) {
                int tmp = (nums[i] > nums[j]) ? L[j] + 1 : 1;
                max_sofar = max(max_sofar, tmp);
            }
            L[i] = max_sofar;
        }

        // Find the max in the DP array
        int max_res = 0;
        for (int k=0; k<n; ++k) {
            if (L[k] > max_res) max_res = L[k];
        }
        return max_res;
    }

    // 贪心 + 二分查找
    // If we want the longest increasing subsequence to be longer, we
    // want the increase to be slower, thus we want every new element
    // in the subsequence to be as small as possible.
    // d[i]: 长度为 i 的 longest increasing subsequence 的末尾元素最小值
    //       [1,2,3], [4,5,6] => d[3] = 3
    // d[i] is monotonously increasing => enables binary search.
    // len: the length of the current LIS.
    // Initialize: len = 1, d[1] = nums[0].
    // Iterate through the array and update d and len.
    //      if nums[i] > d[len], then append nums[i] to d, and len++;
    //      else binary search d for the first element d[j] that's 
    //      smaller then nums[i], and then update d[j+1] = nums[i].
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size(), len = 1;
        if (n == 0) return 0;
        vector<int> d(n+1, 0);
        d[1] = nums[0];
        for (int i=0; i<n; ++i) {
            if (nums[i] > d[len]) {
                d[++len] = nums[i];
            } else {  // binary search
                int l= 1, r = len, pos = 0;
                while (l <= r) {
                    int mid = (l + r) / 2;
                    if (d[mid] < nums[i]) {
                        pos = mid;
                        l = mid + 1;
                    } else {
                        r = mid - 1;
                    }
                }
                d[pos+1] = nums[i];
            }
        }
        return len;
    }
};
